import copy
import time
from collections import defaultdict
from typing import List


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        self.result = []
        self.path = defaultdict(int)

        def dfs(i):
            if i == len(nums):
                if self.path not in self.result:
                    self.result.append(copy.copy(self.path))
                return
            self.path[nums[i]] += 1
            dfs(i + 1)
            self.path[nums[i]] -= 1
            if self.path[nums[i]] == 0:
                del self.path[nums[i]]
            dfs(i + 1)

        dfs(0)
        ans = []
        for d in self.result:
            a = []
            for key, value in d.items():
                for _ in range(value):
                    a.append(key)
            ans.append(a)

        return ans


if __name__ == '__main__':
    time1 = time.time()
    s = Solution()
    r = s.subsetsWithDup(list(range(15)))
    time2 = time.time()
    print(r)
    print(time2 - time1)
